In recent years there has been considerable activity in understanding sensed relative range images. These images comprise data obtained directly by active sensors such as laser rangefinders, or by processing passive sensor data by methods such as stereo vision. As of late, estimating geometric primitives represented by digital range data has been of interest in the robotics industry, the automotive industry, as well as many others especially pertaining to reverse engineering applications.
A geometric primitive is a curve or surface such as a plane, which has a defining equation. For example, a bounded plane is a geometric primitive, and, as well, a single point, or pixel, represented in a Cartesian space is also a geometric primitive. Determining geometric primitives representing or approximating objects within a scanned image often depends on first determining object boundaries so that objects may be isolated from one another.
U.S. Pat. No. 5,142,659, issued Aug. 25, 1992 in the name of Rao et at. entitled Estimation of Local Surface Geometry From Relative Range Images for Object Recognition, describes an apparatus and method for improved segmentation and object recognition. Rao et al. describe objects and background from sensed relative images based on calculations of desired local surface geometry such as local surface orientation, local surface curvature, surface extent and occluding boundaries. The patent specifically focuses on a system which is somewhat tolerant to "rollover", a problem in long distance sensing.
Another patent relating to image processing and image detection is U.S. Pat. No. 5,202,928 in the name of Tomita et al. issued Apr. 13, 1993 entitled Surface Generation Method From Boundaries of Stereo Images. The patent relates specifically to the matching of edges detected in images of the same objects in a three-dimensional scene that are taken simultaneously by two or more image pick-up devices at different positions.
Although both of these patents appear to perform their intended functions, there is a need for an efficient, robust, semi-automatic method for extracting geometric primitives from range data.
It is common for image processing systems relating to three dimensional images, to invoke methods that map pixels, in the form of range image data points to planar surfaces, or to second order or higher order surfaces, thereby approximating range image data points by surfaces. These systems are generally, either automatic or manual and the processes they use are generally classed as fitting processes. In ordinary fitting, an assumption is made that all the points belong to the curve or surface being fit. Automatic systems do not require an operator to intervene or to assist in the processing of image data. Manually driven systems require a skilled user to very accurately select a region in which function approximation is required. For example, an experienced user would typically encircle a region with a mouse, taking great care not to include outlier points not determined to be within the region of interest. For processes that are based on extraction, or robust fitting, this assumption does not hold. Extraction is a generalization of fitting, and is sometimes given the name robust fitting. Thus, an extraction routine must yield not only the equation of the best primitive (curve or surface), but, also specifies which of the data points are described by this primitive. Determining geometric primitives representing or approximating objects within a scanned image by extraction, does not depend on first determining object boundaries to ensure that objects be isolated from one another. The extraction routine in accordance with this invention is tolerant of outlier points that do not belong on a surface patch being approximated, therefore a user of the system described hereafter, is not constrained by required precision of selecting a region accurately as is the case in manual methods. The method in accordance with this invention is semi-automatic.
It is an object of this invention to provide an extraction method which is based on random sampling for surfaces defined both implicitly and parametrically.
It is on object of the invention to provide a semi-automatic method of extracting a geometrical surface from range image data.
It is a further object of the invention to provide a method for determining an equation defining an optimal surface to describe a set of points within a certain tolerance.